Corelab Seminar
2015-2016
Konstantinos Georgiou
Searching with Beachcombers
Abstract.
The Beachcombers' Problem is an optimization problem in which a 1 dimensional domain is to be searched by a set of mobile robots, where each robot has a searching speed $s_i$ and a walking speed $w_i$, such that $s_i$ is less than $w_i$. The search of the domain is completed at the time when each of its points have been searched by at least one of the $n$ robots. We want to develop efficient mobility schedules (algorithms) for the robots which complete the search of the segment as fast as possible.
When the domain is a line segment and all robots start from one of its endpoints, we distinguish between the case that (a) robots are aware of the length of the interval and (b) when the length of the interval is unknown.
For (a) we provide an optimal mobility schedule for arbitrary walking and searching speeds.
For (b) we device a 2 competitive algorithm. When robot's walking speeds are all the same, we show that the competitive ratio is decreasing in the number of robots and approaches 1.29843 as $n$ goes to infinity.
When the domain is a t-star (t line segments with a common endpoint) and robots start from the center, we show, among others, that
(c) the problem is NP-hard even when t=2, and all robots have the same walking speeds.
(d) the problem is tractable when all robots have the same search speeds
(e) the problem admits a highly efficient 1-1/e approximation, asymptotically in t.
This is joint work with J. Czyzowicz, L. Gasieniec, E. Kranakis and F. MacQuarrie